Cook NP 完全性论文

概述

Stephen Cook 于1971年发表的《The Complexity of Theorem-Proving Procedures》，是计算复杂度理论史上最具影响力的文献，首次定义了 NP 完全性概念并证明了 SAT 是第一个 NP 完全问题。

关键内容

论文信息

条目	内容
标题	The Complexity of Theorem-Proving Procedures
作者	Stephen Cook</td> </tr> <tr> <td><strong>发表时间</strong></td> <td>1971年</td> </tr> <tr> <td><strong>会议</strong></td> <td>Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC), pp. 151-158</td> </tr> </tbody> </table> <h3 id="_4">核心贡献</h3> <ul> <li><strong>[[NP 完全性定义：一个问题 L 是 NP 完全的，如果 L ∈ NP 且所有 NP 问题都可以多项式时间归约到 L Cook-Levin 定理：布尔可满足性问题（SAT）是 NP 完全的证明方法：将非确定性图灵机的计算过程编码为布尔公式多项式时间归约：确立了归约作为复杂度比较的工具历史影响 Karp（1972）证明了21个经典组合问题都是 NP 完全的 P vs NP 成为千禧年数学问题（悬赏100万美元） Cook 于1982年获得图灵奖改变了算法研究的方法论来源 raw/books/计算机科学/08-cook-np-completeness.md 相关 Stephen Cook — 作者 NP 完全性 — 论文定义的核心概念 SAT 问题 — 第一个被证明的 NP 完全问题 Cook-Levin 定理 — 论文的核心定理 P vs NP — 论文奠定的问题计算复杂度理论 — 建立的领域 ← Context7 Cook-Levin定理 →

条目

内容

标题

The Complexity of Theorem-Proving Procedures

作者

Stephen Cook</td> </tr> <tr> <td><strong>发表时间</strong></td> <td>1971年</td> </tr> <tr> <td><strong>会议</strong></td> <td>Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC), pp. 151-158</td> </tr> </tbody> </table> <h3 id="_4">核心贡献</h3> <ul> <li><strong>[[NP 完全性定义：一个问题 L 是 NP 完全的，如果 L ∈ NP 且所有 NP 问题都可以多项式时间归约到 L

Cook-Levin 定理：布尔可满足性问题（SAT）是 NP 完全的

证明方法：将非确定性图灵机的计算过程编码为布尔公式

多项式时间归约：确立了归约作为复杂度比较的工具

历史影响

Karp（1972）证明了21个经典组合问题都是 NP 完全的
P vs NP 成为千禧年数学问题（悬赏100万美元）
Cook 于1982年获得图灵奖
改变了算法研究的方法论

来源

raw/books/计算机科学/08-cook-np-completeness.md

Cook NP 完全性论文

概述

关键内容

论文信息

历史影响

来源

相关